/**
 * 有效的括号
 *
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 *
 * 示例 1：
 * 输入：s = "()"
 * 输出：true
 *
 * 示例 2：
 * 输入：s = "()[]{}"
 * 输出：true
 *
 * 示例 3：
 * 输入：s = "(]"
 * 输出：false
 *
 * 示例 4：
 * 输入：s = "([])"
 * 输出：true
 */


import java.util.Stack;

/**
 * 这题是一道典型的用 stack解决的题目, 相信在我们还是小小老子在学习 stack的时候就已经接触过这个题目了吧,
 * 因为我们要判断的是括号是否合法, 如果是合法的括号, 那么中间两个括号一定是匹配的, 所以我们只需要关注最中
 * 间的两个括号, 然后在一个一个向外扩展就好了, 如果碰到了不匹配的括号, 那么就是无效的括号, 要是一直到结束
 * 还没有碰到不匹配的括号, 那么就是有效的括号
 * 这里面有几个要注意的点, 如果全是左括号怎么办, 那么所有的括号就都会进入 stack中, 所以我们要在结束的时候
 * 判断一下 stack是否为空, 要是不为空, 那么就不是有效的括号
 * 另一种情况是当右括号进入的时候, stack中是没有左括号的, 那么在出元素就会异常, 所以在出 stack的时候要判
 * 断是否为空
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */


public class Main {
    public boolean isValid(String s) {

        // 括号数量
        int n = s.length();

        // 定义栈
        Stack<Character> stack = new Stack<>();

        // 遍历括号
        for (int i = 0; i < n; i++) {

            char ch = s.charAt(i);

            // 判断括号是左括号还是右括号
            if (isLeftBracket(ch)) {
                stack.add(ch);
            } else {

                // 判断 stack中是否有元素
                if (stack.size() == 0) {
                    return false;
                }

                // 取出栈顶元素
                char c = stack.pop();

                // 看一下栈顶元素是否与右括号匹配
                if ((c == '(' && ch == ')')
                        || (c == '{' && ch == '}')
                        || (c == '[' && ch == ']')) {

                    // 匹配继续判断下一个元素
                    continue;
                }

                // 不匹配就还是无效括号
                return false;
            }
        }

        // 最后判断下栈里是否还有元素
        if (stack.size() != 0) {

            // 右元素就是无效括号
            return false;
        }
        return true;
    }

    private boolean isLeftBracket (char ch) {
        if (ch == '(' || ch == '{' || ch == '[') {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        Main test = new Main();
        System.out.println(test.isValid("()"));
    }
}